#pragma once
#include<vector>
#include<assert.h>
namespace bit
{
	template <class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;
		template<class Iterator>
		priority_queue(const Iterator& begin, const Iterator& end)
			:_con(begin, end)
		{}
		bool empty() const
		{
			return _con.size() == 0;
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& top() const
		{
			assert(_con.size());
			return _con[0];
		}
		void push(const T& val)
		{
			_con.push_back(val);
			_up(size()-1);
		}
		void pop()
		{
			swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			_down(0);
		}
	private:
		void _up(int child)
		{
			int parent = (child - 1) / 2;
			while (child)
			{
				if (_com(_con[parent], _con[child])) swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void _down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < size())
			{
				if (child +1 < size() && _com(_con[child], _con[child + 1])) child++;
				if (_com(_con[parent], _con[child])) swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
		}
		Container _con;
		Compare _com;
	};
	void priority_queue_test()
	{
		priority_queue<int,vector<int>,greater<int>> q;
		q.push(1);
		q.push(3);
		q.push(2);
		while (q.size())
		{
			cout << q.top() << " ";
			q.pop();
		}
	}
}